#! /usr/bin/env python
#
"""Cyclic sequences factories.

Defines a class `CyclicSequence`, which can be combined with any
sequence-like type to produce a "cyclic" variant, that is, indices wrap
around: if `a` is such a cyclic sequence, then `a[i] == a[i + len(a)]`
for any index `i`.  For example::

  >>> a = CyclicList([0,1,2,3])
  >>> len(a)
  4
  >>> a[1] == a[5]
  True
  >>> a[1] == a[9]
  True

More generally, `a[i] == a[j]` if `i = j mod len(a)`::

  >>> a[5] # == a[2]
  1
  >>> a[-7] # == a[2]
  1

By default, this module exports cyclic variants of the standard
`tuple` and `list` sequences::

  class CyclicTuple(CyclicSequence, tuple): ...
  
  class CyclicList(CyclicSequence, list): ...

`CyclicSequence` assumes that an instance of the base (non-cyclic)
type can be instanciated by passing to it only one argument, namely,
the initialization sequence.  This is how the standard sequence types
`list` and `tuple` behave.
"""
__docformat__ = 'reStructuredText'



import sys

import cython

from native cimport list



## ----------------------------------------------  auxiliary functions
cdef bool _eq(first, second):
    """Return `True` if `first` is sequentially equal to `second`
    with all indices shifted by a fixed amount."""
    if len(second) != len(first):
        return False
    elif None == first._shift_for_sequential_eq(second, 0):
        return False
    else:
        return True

cdef bool _eq_shifted(first, second, int shift):
    """Return `True` if `first` is sequentially equal to `second`
    when shifting all indices by the fixed `shift` amount.
    """
    cdef int l
    cdef int i
    l = (len(first))
    i = (0)
    while i < l:
        if first[i+shift] != second[i]:
            return False
        else:
            i += 1
    return True

cdef int _shift_for_sequential_eq(first, second, int start):
    """Return minimum shift index `b >= start` such that
    `first[b:b+len]==second` as sequential sequences.

    Examples::
      >>> a=CyclicList([1,2,3])
      >>> b=CyclicList([2,3,1])
      >>> a._shift_for_sequential_eq(b,0)
      1
      >>> a._shift_for_sequential_eq(b,2) is None
      True
    """
    cdef int l
    l = (len(first))
    cdef int shift
    shift = (start)
    while shift < l:
        if first._eq_shifted(second, shift):
            return shift
        else:
            shift += 1
    return None
## -----------------------------------------------------------------


cdef class CyclicList(list):

    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__,
                           list.__repr__(self))

    ## item accessors
    ##        
    def __getitem__(self, i):
        return list.__getitem__(self, i % len(self))

    ## slice accessors
    ##    
    def __getslice__(self, i, j):
        """Return [i:j] slice as a base class instance."""
        if j == sys.maxint:
            # __getslice__ is passed `sys.maxint` as second value
            # when taking slices of the form `[n:]`.  In this
            # case, just fall back to standard Python operation.
            return list.__getslice__(self, i, j)
        cdef int a
        cdef int b
        cdef int c
        cdef int l
        cdef int n
        l = (len(self))
        #: sup of the range
        a = (max(i,j))
        #: inf of the range
        b = (min(i,j))
        if (b >= 0) and (a-b < l):
            #: highest multiple of `l` below `a`
            c = (l*(a//l))
            a -= c
            b -= c
            return list.__getslice__(self, b, a)
        else:
            #: how many times the whole seq is repeated in the middle
            n = ((a//l) - (b//l + 1))
            return list.__getslice__(self, b%l,l) \
                   + (n * list.__getslice__(self, 0,l)) \
                   + list.__getslice__(self, 0,a%l)

    ## equality predicates
    ##
    def __hash__(self):
        """Return sum of items in the sequence.

        This is invariant for all permutations, not just the
        cyclic ones, but it is fast and easy to compute.
        """
        # this only works for numeric sequences
        return int(sum(self))

    def __cmp__(self, other):
        """Return 0 if `self` and `other` are equal as cyclic
        sequences; return -1 otherwise, as ordering of cyclic
        sequences is not defined.

        XXX: This is a workaround for Cython forbidding `__eq__` and
        `__ne__` methods in Extension types: defining `__cmp__` is the
        only way to have equality testing work both in pure Python and
        Cython code.
        """
        if _eq(self, other):
            return 0
        else:
            return -1 # XXX: no order defined on cyclic sequences


    ## cpdef int index(self, item, int start=0, int stop=-1):
    ##     """Clone of `list.index` (which see)."""
    ##     if stop == -1:
    ##         stop = len(self)
    ##     while start < stop:
    ##         if self[start] == item:
    ##             return start
    ##         else:
    ##             start += 1
    ##     raise ValueError("CyclicList.index(x): x not in list")


    ## additions to the sequence type
    ##
    cpdef downcast(self):
        """Return instance of base type, with same contents of this object."""
        return list(self)

